/*
*	栈
*/



//删除字符串中的所有相邻重复项
//https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
class Solution {
public:
    string removeDuplicates(string s) {
        string ret;
        for(const auto& c:s)
        {
            if(ret.empty() || c != ret.back()) ret.push_back(c);
            else ret.pop_back();
        }
        return ret;
    }
};



//比较含退格的字符串
//https://leetcode.cn/problems/backspace-string-compare/
class Solution {
public:
    string contrast(string s)
    {
        string tmp;
        tmp.reserve(s.size());
        for (const auto& c : s)
        {
            if (c == '#') { if (!tmp.empty()) tmp.pop_back(); }
            else tmp.push_back(c);
        }
        return tmp;
    }

    bool backspaceCompare(string s, string t) {
        return contrast(s) == contrast(t);
    }
};



//基本计算器
//https://leetcode.cn/problems/basic-calculator-ii/
class Solution {
public:
    int calculate(string s) {
        vector<int> tmp;
        
        int n = s.size();
        int i = 0;
        char op = '+';
        while(i<n)
        {
            if(s[i]>='0' && s[i]<='9')
            {
                int num = 0;
                while(i<n && s[i]>='0' && s[i]<='9') num = (num*10)+(s[i++]-'0');
                if(op == '+') tmp.push_back(num);
                else if(op == '-') tmp.push_back(-num);
                else if(op == '*') tmp.back()*=num;
                else if(op == '/') tmp.back()/=num;
            }
            else
            {
                if(s[i] != ' ') op = s[i];
                ++i;
            }
        }
        int ret = 0;
        for(const auto& x:tmp) ret+=x;
        return ret;
    }
};



//字符串解码
//https://leetcode.cn/problems/decode-string/submissions/
class Solution {
public:
    string decodeString(string s) {
        //因为我们是将处理的字符串放在当前栈顶字符串后 为了防止第一个字符串就需要放置 提前放一个空字符串
        vector<string> vs(1,string());
        vector<int> vi;
        int n = s.size();
        int i = 0;
        while(i<n)
        {
            if(s[i]>='0' && s[i]<='9')
            {
                int num = 0;
                while(i<n&&s[i]>='0'&&s[i]<='9') num=num*10+(s[i++]-'0');
                vi.push_back(num);
            }
            else if(s[i]>='a' && s[i] <= 'z')
            {
                string tmp;
                while(i<n&&s[i]>='a'&&s[i]<='z') tmp.push_back(s[i++]);
                vs.back()+=tmp;
            }
            else if(s[i] == '[')
            {
                ++i;
                string tmp;
                while(i<n&&s[i]>='a'&&s[i]<='z') tmp.push_back(s[i++]);
                vs.push_back(tmp);
            }
            else if(s[i] == ']')
            {
                int num = vi.back();
                vi.pop_back();
                string tmp = vs.back();
                vs.pop_back();
                while(num--) vs.back()+=tmp;
                ++i;
            }
        }
        return vs.back();
    }
};



//验证栈序列
//https://leetcode.cn/problems/validate-stack-sequences/description/
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int n1 = pushed.size();
        int n2 = popped.size();
        int pos1 = 0,pos2 = 0;
        stack<int> st;
        while(pos1 < n1)
        {
            st.push(pushed[pos1++]);
            while(!st.empty() && pos2 < n2 && popped[pos2] == st.top())
            {
                st.pop();
                ++pos2;
            }
        }
        if(pos2 != n2 || !st.empty()) return false;
        return true;
    }
};



